/*
Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,
[1,1,2] have the following unique permutations:
[1,1,2], [1,2,1], and [2,1,1].
*/

class Solution {
public:
    void do_permute(vector<int> &resone, vector<vector<int> > &res, vector<bool> &barray, vector<int> &num) {
        for (int i=0; i < num.size(); i++) {
            // pick next integer
            if (barray[i] ||
                /* skip duplicate number */
                (i && num[i] == num[i-1] && barray[i-1]))
                continue;
            resone.push_back(num[i]);
            barray[i] = true;
            if (resone.size() == num.size()) {
                res.push_back(resone);
            } else {
                do_permute(resone, res, barray, num);
            }
            // reset bit and pop back number
            resone.pop_back();
            barray[i] = false;
        }
    }

    vector<vector<int> > permuteUnique(vector<int> &num) {
        vector<int> resone;
        vector<vector<int> > res;
        vector<bool> barray(num.size(), false);
        sort(num.begin(), num.end());
        do_permute(resone, res, barray, num);
        return res;
    }
};

#if 0
class Solution {
public:
    vector<vector<int> > permuteUnique(vector<int> &num) {
        vector<vector<int> > results;
        int i = num.size() - 1;
        if (i == 0) {
            results.push_back(num);
        } else {
            // sort the array
            sort(num.begin(), num.end());
            results.push_back(num);
            while(nextPermutation(num)) {
                results.push_back(num);
            }
        }
        return results;
    }
private:
    bool nextPermutation(vector<int> &num) {
        // find largest k such as num[k] < num[k+1]
        int k, l, i = num.size()-1;
        while (i > 0 && num[i] <= num[i-1]) { i--; }
        if (i == 0) return false; // no next permutation
        k = i - 1;
        // find largest l such that num[k] < num[l]
        for (l = num.size()-1; l > k; l--) {
            if (num[k] < num[l]) {break;}
        }
        // swap num[k] and num[l]
        swap(num, k, l);
        // reverse num[i] till the end
        int first = i;
        int last = num.size()-1;
        while (first < last) {
            swap(num, first++, last--);
            // first ++; last --;
        }
        return true;
    }
    void swap(vector<int> &num, int k, int l) {
        int temp = num[k];
        num[k] = num[l];
        num[l] = temp;
    }
};
#endif
